package leetcode_401_500;

public class LeeCode_441 {
    public static void main(String[] args) {
//        System.out.println(arrangeCoins(5));
        System.out.println(arrangeCoins(10));
    }
    private static int arrangeCoins(int n) {
        long l = 1, r = n;
        while (l < r){
            long m = l + (r - l) / 2;
            long sum = (m * m + m) / 2;
            if (sum == n){
                return (int) m;
            }else if (sum < n){
                l = m + 1;
            }else {
                r = m - 1;
            }
        }
        if ((l * l + l) / 2 > n){
            return (int) (l - 1);
        }else if ((r * r + r) / 2 <= n){
            return (int) r;
        }
        return 1;
    }
}
